home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / lib / c / etc / regex.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-07-22  |  8.0 KB  |  401 lines
  1. /*
  2.  * Copyright (c) 1980 Regents of the University of California.
  3.  * All rights reserved.  The Berkeley software License Agreement
  4.  * specifies the terms and conditions for redistribution.
  5.  */
  6.  
  7. #if defined(LIBC_SCCS) && !defined(lint)
  8. static char sccsid[] = "@(#)regex.c    5.2 (Berkeley) 3/9/86";
  9. #endif LIBC_SCCS and not lint
  10.  
  11. /*
  12.  * routines to do regular expression matching
  13.  *
  14.  * Entry points:
  15.  *
  16.  *    re_comp(s)
  17.  *        char *s;
  18.  *     ... returns 0 if the string s was compiled successfully,
  19.  *             a pointer to an error message otherwise.
  20.  *         If passed 0 or a null string returns without changing
  21.  *           the currently compiled re (see note 11 below).
  22.  *
  23.  *    re_exec(s)
  24.  *        char *s;
  25.  *     ... returns 1 if the string s matches the last compiled regular
  26.  *               expression, 
  27.  *             0 if the string s failed to match the last compiled
  28.  *               regular expression, and
  29.  *            -1 if the compiled regular expression was invalid 
  30.  *               (indicating an internal error).
  31.  *
  32.  * The strings passed to both re_comp and re_exec may have trailing or
  33.  * embedded newline characters; they are terminated by nulls.
  34.  *
  35.  * The identity of the author of these routines is lost in antiquity;
  36.  * this is essentially the same as the re code in the original V6 ed.
  37.  *
  38.  * The regular expressions recognized are described below. This description
  39.  * is essentially the same as that for ed.
  40.  *
  41.  *    A regular expression specifies a set of strings of characters.
  42.  *    A member of this set of strings is said to be matched by
  43.  *    the regular expression.  In the following specification for
  44.  *    regular expressions the word `character' means any character but NUL.
  45.  *
  46.  *    1.  Any character except a special character matches itself.
  47.  *        Special characters are the regular expression delimiter plus
  48.  *        \ [ . and sometimes ^ * $.
  49.  *    2.  A . matches any character.
  50.  *    3.  A \ followed by any character except a digit or ( )
  51.  *        matches that character.
  52.  *    4.  A nonempty string s bracketed [s] (or [^s]) matches any
  53.  *        character in (or not in) s. In s, \ has no special meaning,
  54.  *        and ] may only appear as the first letter. A substring 
  55.  *        a-b, with a and b in ascending ASCII order, stands for
  56.  *        the inclusive range of ASCII characters.
  57.  *    5.  A regular expression of form 1-4 followed by * matches a
  58.  *        sequence of 0 or more matches of the regular expression.
  59.  *    6.  A regular expression, x, of form 1-8, bracketed \(x\)
  60.  *        matches what x matches.
  61.  *    7.  A \ followed by a digit n matches a copy of the string that the
  62.  *        bracketed regular expression beginning with the nth \( matched.
  63.  *    8.  A regular expression of form 1-8, x, followed by a regular
  64.  *        expression of form 1-7, y matches a match for x followed by
  65.  *        a match for y, with the x match being as long as possible
  66.  *        while still permitting a y match.
  67.  *    9.  A regular expression of form 1-8 preceded by ^ (or followed
  68.  *        by $), is constrained to matches that begin at the left
  69.  *        (or end at the right) end of a line.
  70.  *    10. A regular expression of form 1-9 picks out the longest among
  71.  *        the leftmost matches in a line.
  72.  *    11. An empty regular expression stands for a copy of the last
  73.  *        regular expression encountered.
  74.  */
  75.  
  76. /*
  77.  * constants for re's
  78.  */
  79. #define    CBRA    1
  80. #define    CCHR    2
  81. #define    CDOT    4
  82. #define    CCL    6
  83. #define    NCCL    8
  84. #define    CDOL    10
  85. #define    CEOF    11
  86. #define    CKET    12
  87. #define    CBACK    18
  88.  
  89. #define    CSTAR    01
  90.  
  91. #define    ESIZE    512
  92. #define    NBRA    9
  93.  
  94. static    int advance();
  95. static    char    expbuf[ESIZE], *braslist[NBRA], *braelist[NBRA];
  96. static    char    circf;
  97.  
  98. /*
  99.  * compile the regular expression argument into a dfa
  100.  */
  101. char *
  102. re_comp(sp)
  103.     register char    *sp;
  104. {
  105.     register int    c;
  106.     register char    *ep = expbuf;
  107.     int    cclcnt, numbra = 0;
  108.     char    *lastep = 0;
  109.     char    bracket[NBRA];
  110.     char    *bracketp = &bracket[0];
  111.     static    char    *retoolong = "Regular expression too long";
  112.  
  113. #define    comerr(msg) {expbuf[0] = 0; numbra = 0; return(msg); }
  114.  
  115.     if (sp == 0 || *sp == '\0') {
  116.         if (*ep == 0)
  117.             return("No previous regular expression");
  118.         return(0);
  119.     }
  120.     if (*sp == '^') {
  121.         circf = 1;
  122.         sp++;
  123.     }
  124.     else
  125.         circf = 0;
  126.     for (;;) {
  127.         if (ep >= &expbuf[ESIZE])
  128.             comerr(retoolong);
  129.         if ((c = *sp++) == '\0') {
  130.             if (bracketp != bracket)
  131.                 comerr("unmatched \\(");
  132.             *ep++ = CEOF;
  133.             *ep++ = 0;
  134.             return(0);
  135.         }
  136.         if (c != '*')
  137.             lastep = ep;
  138.         switch (c) {
  139.  
  140.         case '.':
  141.             *ep++ = CDOT;
  142.             continue;
  143.  
  144.         case '*':
  145.             if (lastep == 0 || *lastep == CBRA || *lastep == CKET)
  146.                 goto defchar;
  147.             *lastep |= CSTAR;
  148.             continue;
  149.  
  150.         case '$':
  151.             if (*sp != '\0')
  152.                 goto defchar;
  153.             *ep++ = CDOL;
  154.             continue;
  155.  
  156.         case '[':
  157.             *ep++ = CCL;
  158.             *ep++ = 0;
  159.             cclcnt = 1;
  160.             if ((c = *sp++) == '^') {
  161.                 c = *sp++;
  162.                 ep[-2] = NCCL;
  163.             }
  164.             do {
  165.                 if (c == '\0')
  166.                     comerr("missing ]");
  167.                 if (c == '-' && ep [-1] != 0) {
  168.                     if ((c = *sp++) == ']') {
  169.                         *ep++ = '-';
  170.                         cclcnt++;
  171.                         break;
  172.                     }
  173.                     while (ep[-1] < c) {
  174.                         *ep = ep[-1] + 1;
  175.                         ep++;
  176.                         cclcnt++;
  177.                         if (ep >= &expbuf[ESIZE])
  178.                             comerr(retoolong);
  179.                     }
  180.                 }
  181.                 *ep++ = c;
  182.                 cclcnt++;
  183.                 if (ep >= &expbuf[ESIZE])
  184.                     comerr(retoolong);
  185.             } while ((c = *sp++) != ']');
  186.             lastep[1] = cclcnt;
  187.             continue;
  188.  
  189.         case '\\':
  190.             if ((c = *sp++) == '(') {
  191.                 if (numbra >= NBRA)
  192.                     comerr("too many \\(\\) pairs");
  193.                 *bracketp++ = numbra;
  194.                 *ep++ = CBRA;
  195.                 *ep++ = numbra++;
  196.                 continue;
  197.             }
  198.             if (c == ')') {
  199.                 if (bracketp <= bracket)
  200.                     comerr("unmatched \\)");
  201.                 *ep++ = CKET;
  202.                 *ep++ = *--bracketp;
  203.                 continue;
  204.             }
  205.             if (c >= '1' && c < ('1' + NBRA)) {
  206.                 *ep++ = CBACK;
  207.                 *ep++ = c - '1';
  208.                 continue;
  209.             }
  210.             *ep++ = CCHR;
  211.             *ep++ = c;
  212.             continue;
  213.  
  214.         defchar:
  215.         default:
  216.             *ep++ = CCHR;
  217.             *ep++ = c;
  218.         }
  219.     }
  220. }
  221.  
  222. /* 
  223.  * match the argument string against the compiled re
  224.  */
  225. int
  226. re_exec(p1)
  227.     register char    *p1;
  228. {
  229.     register char    *p2 = expbuf;
  230.     register int    c;
  231.     int    rv;
  232.  
  233.     for (c = 0; c < NBRA; c++) {
  234.         braslist[c] = 0;
  235.         braelist[c] = 0;
  236.     }
  237.     if (circf)
  238.         return((advance(p1, p2)));
  239.     /*
  240.      * fast check for first character
  241.      */
  242.     if (*p2 == CCHR) {
  243.         c = p2[1];
  244.         do {
  245.             if (*p1 != c)
  246.                 continue;
  247.             if (rv = advance(p1, p2))
  248.                 return(rv);
  249.         } while (*p1++);
  250.         return(0);
  251.     }
  252.     /*
  253.      * regular algorithm
  254.      */
  255.     do
  256.         if (rv = advance(p1, p2))
  257.             return(rv);
  258.     while (*p1++);
  259.     return(0);
  260. }
  261.  
  262. /* 
  263.  * try to match the next thing in the dfa
  264.  */
  265. static    int
  266. advance(lp, ep)
  267.     register char    *lp, *ep;
  268. {
  269.     register char    *curlp;
  270.     int    ct, i;
  271.     int    rv;
  272.  
  273.     for (;;)
  274.         switch (*ep++) {
  275.  
  276.         case CCHR:
  277.             if (*ep++ == *lp++)
  278.                 continue;
  279.             return(0);
  280.  
  281.         case CDOT:
  282.             if (*lp++)
  283.                 continue;
  284.             return(0);
  285.  
  286.         case CDOL:
  287.             if (*lp == '\0')
  288.                 continue;
  289.             return(0);
  290.  
  291.         case CEOF:
  292.             return(1);
  293.  
  294.         case CCL:
  295.             if (cclass(ep, *lp++, 1)) {
  296.                 ep += *ep;
  297.                 continue;
  298.             }
  299.             return(0);
  300.  
  301.         case NCCL:
  302.             if (cclass(ep, *lp++, 0)) {
  303.                 ep += *ep;
  304.                 continue;
  305.             }
  306.             return(0);
  307.  
  308.         case CBRA:
  309.             braslist[*ep++] = lp;
  310.             continue;
  311.  
  312.         case CKET:
  313.             braelist[*ep++] = lp;
  314.             continue;
  315.  
  316.         case CBACK:
  317.             if (braelist[i = *ep++] == 0)
  318.                 return(-1);
  319.             if (backref(i, lp)) {
  320.                 lp += braelist[i] - braslist[i];
  321.                 continue;
  322.             }
  323.             return(0);
  324.  
  325.         case CBACK|CSTAR:
  326.             if (braelist[i = *ep++] == 0)
  327.                 return(-1);
  328.             curlp = lp;
  329.             ct = braelist[i] - braslist[i];
  330.             while (backref(i, lp))
  331.                 lp += ct;
  332.             while (lp >= curlp) {
  333.                 if (rv = advance(lp, ep))
  334.                     return(rv);
  335.                 lp -= ct;
  336.             }
  337.             continue;
  338.  
  339.         case CDOT|CSTAR:
  340.             curlp = lp;
  341.             while (*lp++)
  342.                 ;
  343.             goto star;
  344.  
  345.         case CCHR|CSTAR:
  346.             curlp = lp;
  347.             while (*lp++ == *ep)
  348.                 ;
  349.             ep++;
  350.             goto star;
  351.  
  352.         case CCL|CSTAR:
  353.         case NCCL|CSTAR:
  354.             curlp = lp;
  355.             while (cclass(ep, *lp++, ep[-1] == (CCL|CSTAR)))
  356.                 ;
  357.             ep += *ep;
  358.             goto star;
  359.  
  360.         star:
  361.             do {
  362.                 lp--;
  363.                 if (rv = advance(lp, ep))
  364.                     return(rv);
  365.             } while (lp > curlp);
  366.             return(0);
  367.  
  368.         default:
  369.             return(-1);
  370.         }
  371. }
  372.  
  373. backref(i, lp)
  374.     register int    i;
  375.     register char    *lp;
  376. {
  377.     register char    *bp;
  378.  
  379.     bp = braslist[i];
  380.     while (*bp++ == *lp++)
  381.         if (bp >= braelist[i])
  382.             return(1);
  383.     return(0);
  384. }
  385.  
  386. int
  387. cclass(set, c, af)
  388.     register char    *set, c;
  389.     int    af;
  390. {
  391.     register int    n;
  392.  
  393.     if (c == 0)
  394.         return(0);
  395.     n = *set++;
  396.     while (--n)
  397.         if (*set++ == c)
  398.             return(af);
  399.     return(! af);
  400. }
  401.